package com.yww.leetcode.hashtable;

import java.util.HashSet;

/**
 * @author yww
 * @description 136. 只出现一次的数字
 * @since 2024/2/22 11:35
 */
public class SingleNumber136 {
    // 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，
    // 其余每个元素均出现两次。找出那个只出现了一次的元素。
    public int singleNumber(int[] nums) {
        return singleNumber2(nums);
    }

    /*
       思路1
       1. 准备一个 Set 集合，逐一放入数组元素
       2. 遇到重复的，则删除
       3. 最后留下来的，就是那个没有重复的数字

    */
    public int singleNumber1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                set.remove(num);
            }
        }
        return set.toArray(new Integer[]{})[0];
    }

    /*
        思路2
        1. 任何相同的数字异或，结果都是 0
        2. 任何数字与 0 异或，结果是数字本身
        3. ^ 异或满足交换律， 即，3^3^1=1 == 3^1^3=1
     */
    public int singleNumber2(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res = res ^ num;
        }
        return res;
    }
}
